class Solution {
 public:
  // 不对中节点做处理，所以前中后序都可以
  /*
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1 && !root2) return nullptr;
    if (!root1) return root2;
    if (!root2) return root1;
    root1->val += root2->val;
    root1->left = mergeTrees(root1->left, root2->left);
    root1->right = mergeTrees(root1->right, root2->right);
    return root1;
  }
  */
  /*
  //使用栈模拟深度优先遍历
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if(!root1) return root2;
    if(!root2) return root1;
  stack<pair<TreeNode*, TreeNode*>> st;
  st.push({root1, root2});
  TreeNode* temp1;
  TreeNode* temp2;
  while (!st.empty()) {
    auto [temp1, temp2] = st.top();
    st.pop();

    // temp1->val += temp2->val;
    if(temp1->left&&temp2->left)
        st.push(make_pair(temp1->left,temp2->left));
    if(!temp1->left)
        temp1->left=temp2->left;
    // temp1->val += temp2->val;
    if(temp1->right&&temp2->right)
        st.push(make_pair(temp1->right,temp2->right));
    if(!temp1->right)
        temp1->right=temp2->right;

    temp1->val += temp2->val;
    }
  return root1;
  }
  */
  // 使用队列
  TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
    if (!root1) return root2;
    if (!root2) return root1;
    queue<pair<TreeNode*, TreeNode*>> que;
    que.push({root1, root2});
    TreeNode* temp1;
    TreeNode* temp2;
    while (!que.empty()) {
      auto [temp1, temp2] = que.front();
      que.pop();

      temp1->val += temp2->val;
      if (temp1->left && temp2->left)
        que.push(make_pair(temp1->left, temp2->left));
      if (!temp1->left) temp1->left = temp2->left;
      // temp1->val += temp2->val;
      if (temp1->right && temp2->right)
        que.push(make_pair(temp1->right, temp2->right));
      if (!temp1->right) temp1->right = temp2->right;
      // temp1->val += temp2->val;
    }
    return root1;
  }
};